// 给你一个整数数组 cost ，
// 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
// 一旦你支付此费用，即可选择向上爬一个或者两个台阶。
// 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
// 请你计算并返回达到楼梯顶部的最低花费。
// 来源：力扣（LeetCode）
// 链接：https://leetcode.cn/problems/min-cost-climbing-stairs
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

// 1. 写出尝试函数 helper
//  1.1 明确 helper 的定义：到达楼梯 i 的花费
//  1.2 分析状态参数和变化范围: i 范围是[0, cost.length - 1]
//  1.3 分析 helper 和 子问题的关系：helper(i) 只与 helper(i - 1) helper(i - 2) 有关
//  1.4 分析 base case：helper(0) helper(1) 是 0
// 2. 画出表格分析依赖方向
// 3. 写成动态规划形式

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
  const len = cost.length
  const dp = new Array(len).fill(0)
  dp[0] = dp[1] = 0
  for (let i = 2; i <= len; i++) {
    const p1 = dp[i - 1] + cost[i - 1]
    const p2 = dp[i - 2] + cost[i - 2]

    dp[i] = Math.min(p1, p2)
  }
  return dp[len]

  // 1. 到达楼梯i 的花费
  const helper = (i) => {
    // 仔细阅读题目发现，可以从楼梯0 和 楼梯1 直接出发
    // 也就是说到达 楼梯0 和 楼梯1 的花费其实是 0
    if (i === 0 || i === 1) {
      return 0
    }

    // 到达楼梯 i，
    // 可以从 楼梯 i - 1 花费 cost[i - 1] 跳上来
    // 也可以从 楼梯 i - 2 花费 cost[i - 2] 跳上来
    const p1 = helper(i - 1) + cost[i - 1]
    const p2 = helper(i - 2) + cost[i - 2]

    return Math.min(p1, p2)
  }
  // 题目要求的是爬完楼梯，所以结果不是 helper(len - 1) 而是 helper(len)
  const res = helper(len)

  return res
}


console.log(
  minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])
)